#include<iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        ListNode dump(INT32_MIN);
        dump.next = head;
        ListNode* prev = &dump;
        ListNode* cur = dump.next;
        while (cur != NULL) {
            if (prev->val > cur->val) {
                ListNode* tmp = &dump;
                while (tmp->next->val < cur->val)
                    tmp = tmp->next;
                prev->next = cur->next;
                cur->next = tmp->next;
                tmp->next = cur;
                cur = prev->next;
            }
            else {
                prev = cur;
                cur = cur->next;
            }
        }
        return dump.next;
    }
};